package com.code.test.first.greedy;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.md
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 * <p>
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 * <p>
 * 每个孩子至少分配到 1 个糖果。
 * 相邻的孩子中，评分高的孩子必须获得更多的糖果。
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,0,2]
 * 输出: 5
 * 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
 * 示例 2:
 * <p>
 * 输入: [1,2,2]
 * 输出: 4
 * 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
 */
public class Code135 {

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 5, 2};
        int ret = candy(nums);
        System.out.println(ret);
    }

    /**
     * 每个人最少1个，相邻的如果比对方高，则需要多一个
     * 从左向右，保证每个人多一个，右边比左边高，右边多一个
     * 从右向左，保证左边比右边高，左边要多一个
     */
    public static int candy(int[] nums) {
        int len = nums.length;
        int[] candy = new int[len];
        candy[0] = 1;
        for (int i = 1; i < len; i++) {
            //从左向右，右边比左边大的都加一
            if (nums[i] > nums[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            } else {
                //保证每个孩子至少有1个糖果
                candy[i] = 1;
            }
        }
        //从倒数第二个开始从右往左遍历
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) {
                //当左边比右边大时，保证左边多一个
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        int ret = 0;
        for (int i : candy) {
            ret += i;
        }
        return ret;
    }

}
